
// 1312.让字符串成为回文串的最少插入次数
class Solution {
public:
    int minInsertions(string s) {
        // 此题依旧是找出字符串的最长回文序列即可
        int n = s.size();
        vector<vector<int>> dp(n ,vector<int>(n,1));          // 其中dp[i][j]表示[j,i]中最长的回文子串的长度
        int len = 1;
        for(int i = 1 ; i < n ; i++)
        {
            for(int j = i - 1 ; j >= 0 ;j--)
            {
                if(s[i] == s[j] && j + 1 == i) dp[i][j] = 2;
                else if(s[i] == s[j] ) dp[i][j] = dp[i - 1][j + 1] + 2;
                else if(s[i] != s[j]) dp[i][j] = max(dp[i - 1][j] , dp[i][j + 1]);
                len = max(len , dp[i][j]);
            }
        }
        return n - len;
    }
};